#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>



char lookahead;

enum TERMINAL {

    ID,

	ADD,

	MUL,

	LBR,

	RBR,

	END,

	ERR

};



enum NON_TERMINAL {

	E,

	T,

	F

};



enum ACTION_TYPE {

	SHIFT,

	REDUCE,

	ERROR,

	ACC

};



#define NUM_TERMINAL  6

#define NUM_NONTERMINAL  3

#define NUM_STATES  12



struct action{

	enum ACTION_TYPE type;

	int id;

}  actionTable[NUM_STATES][NUM_TERMINAL];



int gotoTable[NUM_STATES][NUM_NONTERMINAL];



int stackPtr;

int stack[1024];

void push(int state) {

	stack[stackPtr] = state;

	stackPtr ++;

}



void pop() {

	stackPtr --;

}



int top() {

	return stack[stackPtr - 1];

}



void init() {

	int i, j;



	//stack

	stackPtr = 0;

	push(0);



	//action and goto tables

	for(i = 0; i < NUM_STATES; i ++) {

		for(j = 0; j < NUM_TERMINAL; j ++) {

		actionTable[i][j].type = ERROR;

		}

		for(j = 0; j < NUM_NONTERMINAL; j ++) {

		gotoTable[i][j] = -1;

		}

	}



	//fill in the goto table

	gotoTable[0][E] = 1;

	gotoTable[0][T] = 2;

	gotoTable[0][F] = 3;

	gotoTable[4][E]=8;

	gotoTable[4][T]=2;

	gotoTable[4][F]=3;

	gotoTable[6][T]=9;

	gotoTable[6][F]=3;

	gotoTable[7][F]=10;

	//... your turn





	//fill in the action table

	actionTable[2][ADD].type = REDUCE;

	actionTable[2][ADD].id = 2;

	actionTable[2][MUL].type = SHIFT;

	actionTable[2][MUL].id = 7;

	actionTable[2][RBR].type = REDUCE;

	actionTable[2][RBR].id = 2;

	actionTable[2][END].type = REDUCE;

	actionTable[2][END].id = 2;

	actionTable[0][ID].type=SHIFT;

	actionTable[0][ID].id=5;

	actionTable[0][LBR].type=SHIFT;

	actionTable[0][LBR].id=4;

	actionTable[1][ADD].type=SHIFT;

	actionTable[1][ADD].id=6;

        actionTable[1][END].type=ACC;

	actionTable[3][ADD].type=REDUCE;

	actionTable[3][ADD].id=4;

	actionTable[3][MUL].type=REDUCE;

	actionTable[3][MUL].id=4;

	actionTable[3][RBR].type=REDUCE;

	actionTable[3][RBR].id=4;

	actionTable[3][END].type=REDUCE;

	actionTable[3][END].id=4;

	actionTable[4][ID].type=SHIFT;

	actionTable[4][ID].id=5;

	actionTable[4][LBR].type=SHIFT;

	actionTable[4][LBR].id=4;

	actionTable[5][ADD].type=REDUCE;

	actionTable[5][ADD].id=6;

	actionTable[5][MUL].type=REDUCE;

	actionTable[5][MUL].id=6;

	actionTable[5][RBR].type=REDUCE;

	actionTable[5][RBR].id=6;

        actionTable[5][END].type=REDUCE;

	actionTable[5][END].id=6;

        actionTable[6][ID].type=SHIFT;

	actionTable[6][ID].id=5;

	actionTable[6][LBR].type=SHIFT;

	actionTable[6][LBR].id=4;

	actionTable[7][ID].type=SHIFT;

	actionTable[7][ID].id=5;

	actionTable[7][LBR].type=SHIFT;

	actionTable[7][LBR].id=4;

	actionTable[8][ADD].type=SHIFT;

	actionTable[8][ADD].id=6;

	actionTable[8][RBR].type=SHIFT;

	actionTable[8][RBR].id=11;

	actionTable[9][ADD].type=REDUCE;

	actionTable[9][ADD].id=1;

	actionTable[9][MUL].type=SHIFT;

	actionTable[9][MUL].id=7;

	actionTable[9][RBR].type=REDUCE;

	actionTable[9][RBR].id=1;

	actionTable[9][END].type=REDUCE;

	actionTable[9][END].id=1;

        actionTable[10][ADD].type=REDUCE;

	actionTable[10][ADD].id=3;

	actionTable[10][MUL].type=REDUCE;

	actionTable[10][MUL].id=3;

	actionTable[10][RBR].type=REDUCE;

	actionTable[10][RBR].id=3;

	actionTable[10][END].type=REDUCE;

	actionTable[10][END].id=3;

	actionTable[11][ADD].type=REDUCE;

	actionTable[11][ADD].id=5;

	actionTable[11][MUL].type=REDUCE;

	actionTable[11][MUL].id=5;

	actionTable[11][RBR].type=REDUCE;

	actionTable[11][RBR].id=5;

	actionTable[11][END].type=REDUCE;

	actionTable[11][END].id=5;



	//... your turn

}



enum TERMINAL lexical(FILE *fp) {



	lookahead = getc(fp);



	while(lookahead == ' ' || lookahead == '\t' || lookahead == '\n') {

		lookahead = getc(fp);

	}



	if(isdigit(lookahead)) {

		while(isdigit(lookahead)) {

			lookahead = getc(fp);

		}

		ungetc(lookahead, fp);

		return ID;

	} else if (lookahead == '+') {

		return ADD;

	} else if (lookahead == '*') {

		return MUL;

	} else if(lookahead == EOF) {

		return END;

	}else if(lookahead == '(') {

		return LBR;

	} else if(lookahead == ')') {

		return RBR;

	} else {

		return ERR;

	}

}



void parse(enum TERMINAL *input) {

	int currentState = 0;

	int index = 0;



	while(1) {

		printf("currentState: %d\n", currentState);

		switch(actionTable[currentState][input[index]].type) {

			case SHIFT:

			   	

				currentState=actionTable[currentState][input[index]].id;

				push(currentState);//how to shift

			        index++; 

			        break;

			case REDUCE:

				switch(actionTable[currentState][input[index]].id) {

					case 1:

						pop();

						pop();

						pop();

						currentState=gotoTable[top()][E];

						push(currentState);//reduce by production 1

						break;

					case 2:

					        pop();

						currentState=gotoTable[top()][E];

						push(currentState);

						//reduce by production 2

						break;

					case 3:

					        pop();

						pop();

						pop();

						currentState=gotoTable[top()][T];

						push(currentState);

						//reduce by production 3

						break;

					case 4:

					        pop();

						currentState=gotoTable[top()][T];

						push(currentState);

						//reduce by production 4

						break;

					case 5:

					        pop();

						pop();

						pop();

						currentState=gotoTable[top()][F];

						push(currentState);

						//reduce by production 4

						break;

					case 6:

					        pop();

						currentState=gotoTable[top()][F];

						push(currentState);

						//reduce by production 4

						break;

					default:

						printf("ERROR REDUCE\n");

						exit(-1);

						break;

				}

				break;

			case ERROR:

				printf("ERROR ACTION\n");

				exit(-1);

				break;

			case ACC:

				if(input[index] == END) {

					printf("ACC\n");

					return;

				} else {

					printf("ERROR ACC\n");

					exit(-1);

				}

				break;

		}

	}

}





int main(int argc, char **argv) {

	enum TERMINAL input[1024]; 

	int inputIndex = 0;

	FILE *fp;

	enum TERMINAL temp;

	if(argc < 2) {

		printf("insufficient arguments");

		return 1;

	}

	fp = fopen(argv[1], "r");

	while((temp = lexical(fp)) != END) {

		input[inputIndex++] = temp;

	}



	input[inputIndex] = END;

	fclose(fp);



	init();

	parse(input);



	return 0;

}

